package com.sicheng.lc.周赛.分类.思维;


import java.util.HashMap;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/12 20:46
 */
public class 公司命名 {
    //https://leetcode.cn/contest/weekly-contest-297/problems/naming-a-company/
    public static void main(String[] args) {

        公司命名 solution = new 公司命名();
//        String[] ideas = {"lack", "back"};
        String[] ideas = {"coffee", "donuts", "time", "toffee"};
        System.out.println(solution.distinctNames(ideas));
        System.out.println();
    }

    public long distinctNames(String[] ideas) {

        // ideas= axx,bxx,cyy,ayy,dyy===> group{cyy,ayy,byy},{axx,bxx}
        // 大致思路
        // 1.按照单词后缀来分组,同一组不可以互换
        // 技巧: 将分到同一组的单词首字母 压缩到一个32位的数
        HashMap<String, Integer> group = new HashMap<>();
        for (String idea : ideas) {
            String key = idea.substring(1);
            int x = group.getOrDefault(key, 0);
            x |= 1 << (idea.charAt(0) - 'a');
            group.put(key, x);
        }
        // 2.不同组A,B要想互换的条件  换的是首字母
        // ===>  i -> j 在A组里要有i字符,无j字符
        // ===>         在B组里无i字符，有j字符
        int[][] cnt = new int[26][26];

        long res = 0;
        // 这个遍历非常不好想,顺着group依次遍历
        // 统计每一个group的状态,有i无j时 统计个数
        //                    无i有j是 计算结果将以前的group的有i无j的首字母换到我这里来
        for (int state : group.values()) {
            for (int i = 0; i < 26; i++) {
                if ((state >> i & 1) == 1) {
                    for (int j = 0; j < 26; j++) {
                        if ((state >> j & 1) == 0) {
                            //state 有i无j
                            cnt[i][j]++;
                        }
                    }
                } else {
                    for (int j = 0; j < 26; j++) {
                        if ((state >> j & 1) == 1) {
                            //state 无i有j 我就想换以前组的有i无j的个数
                            res += cnt[i][j];
                        }
                    }
                }
            }
        }


        // 结果是res的2倍  其实就是互换单词只统计了一次 a->b,b->a  实际上换了2次
        return res << 1;
    }


}
